package pers.qianyu.month_202101.date_20210125;

import org.junit.*;

import java.util.*;

/**
 * 剑指 Offer 13. 机器人的运动范围
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 *
 * @author mizzle rain
 * @date 2021-01-25 11:29
 */
public class MovingCount {
    int[][] dxy = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    boolean isValid(int x, int y, int k) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x = x / 10;
        }
        while (y > 0) {
            sum += y % 10;
            y = y / 10;
        }
        return sum <= k;
    }

    public int movingCount(int k, int m, int n) {
        if (m == 0 || n == 0) return 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        q.add(new int[]{0, 0});
        int res = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            if (visited[cur[0]][cur[1]] || !isValid(cur[0], cur[1], k)) continue;
            res++;
            visited[cur[0]][cur[1]] = true;
            for (int[] dis : dxy) {
                int x = cur[0] + dis[0], y = cur[1] + dis[1];
                if (x >= 0 && y >= 0 && x < m && y < n) {
                    q.add(new int[]{x, y});
                }
            }
        }
        return res;
    }

    @Test
    public void test1() {
        int result = new MovingCount().movingCount(2, 3, 1);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        boolean result = new MovingCount().isValid(1, 1, 1);
        System.out.println("result = " + result);
    }
}
